package com.shawn.algorithm.back;

public class Pattern {

	private boolean matched = false;

	/**
	 * 正则表达式
	 */
	private char[] pattern;

	public Pattern(String pattern) {
		if (pattern == null) {
			throw new NullPointerException();
		}
		this.pattern = pattern.toCharArray();
	}

	public boolean match(char[] text, int tlen) {
		matched = false;
		rmatch(0, 0, text, tlen);
		return matched;
	}

	private void rmatch(int ti, int pj, char[] text, int tlen) {
		if (matched) {
			return;
		}
		final int length = pattern.length;
		if (pj == length) {
			if (ti == tlen) {
				matched = true;
			}
			return;
		}

		if (pattern[pj] == '*') {
			for (int k = 0; k <= tlen - ti; k++) {
				rmatch(ti + k, pj + 1, text, tlen);
			}
		} else if (pattern[pj] == '?') {
			rmatch(ti, pj + 1, text, tlen);
			rmatch(ti + 1, pj + 1, text, tlen);
		} else if (ti < tlen && pattern[pj] == text[ti]) {
			rmatch(ti + 1, pj + 1, text, tlen);
		}
	}
}
